package algorithm_demo.demo03;

/**
 * 是否满二叉树
 * 给定一棵二叉树的头节点head，返回这颗二叉树是不是满二叉树
 * 有2h - 1个节点 就是满二叉树 h表示高度 节点数为N
 *
 * @author Api
 * @date 2023/2/12 11:24
 */
public class Code04_IsFull {
    public static class Node {
        int value;
        Node left;
        Node right;

        public Node(int value) {
            this.value = value;
        }
    }

    public static class Info {
        public int height;
        public int nodes;


        public Info(int height, int nodes) {
            this.height = height;
            this.nodes = nodes;
        }
    }

    public static boolean isFull(Node x) {
        if (x == null) {
            return true;
        }
        Info all = process(x);
        return (1 << all.height) - 1 == all.nodes;
    }


    public static Info process(Node x) {
        if (x == null) {
            return new Info(0, 0);
        }
        Info leftInfo = process(x.left);
        Info rightInfo = process(x.right);
        //二叉树高度都这样
        int height = Math.max(leftInfo.height, rightInfo.height) + 1;
        int nodes = leftInfo.nodes + rightInfo.nodes + 1;
        return new Info(height, nodes);
    }
}
